package com.tgy.leetcode;

import java.util.Arrays;

/**
 * @Author: tgy
 * @Date: 1/8/21 1:56 PM
 *
 * https://leetcode-cn.com/problems/coin-change-2/
 */
public class _518_零钱兑换_II {

    public int change(int amount, int[] coins) {


        if (coins == null) {

            return 0;
        }

        int[][] dp = new int[amount + 1][coins.length + 1];

        for (int i = 0; i < dp[0].length; i++) {

            dp[0][i] = 1;
        }

        for (int i = 1; i < dp.length; i++) {

            for (int j = coins.length - 1; j >= 0 ; j--) {

                System.out.println(i + ":" + j);
                dp[i][j] = dp[i][j+1];

                if (i >= coins[j]) {

                    dp[i][j] += dp[i - coins[j]][j+1];
                }
            }

        }

        for (int i = 0; i < dp.length; i++) {

            System.out.println(Arrays.toString(dp[i]));
        }

        return dp[amount][0];
    }

    public int change02(int amount, int[] coins) {


        if (coins == null) {

            return 0;
        }

        int[][] dp = new int[coins.length + 1][amount + 1];

        for (int i = 0; i < dp.length; i++) {

            dp[i][0] = 1;
        }


        /**
         * int sum = 0;
         *         for (int i = 0; i * coins[index] <= rest; i++) {
         *
         *             sum += find(coins,index+1,rest - i*coins[index]);
         *         }
         *
         *         return sum;
         */


        for (int i = coins.length - 1; i >= 0 ; i--) {

            for (int j = 1; j <= amount; j++) {

                /**
                 * 不选 i
                 */
                dp[i][j] = dp[i+1][j];

                /**
                 * 可以选 coins[i]
                 */
                if (j >= coins[i]) {

                    dp[i][j] += dp[i][j - coins[i]];
                }

            }
        }

//        for (int i = 0; i < dp.length; i++) {
//
//            System.out.println(Arrays.toString(dp[i]));
//        }

        return dp[0][amount];
    }

    public int change01(int amount, int[] coins) {

        if (coins == null) {

            return 0;
        }

        return find(coins,0,amount);
    }


    private int find(int[] coins, int index, int rest) {


        if (index == coins.length) {

            return rest==0?1:0;
        }


        if (rest == 0) {

            return 1;
        }

        int sum = 0;
        for (int i = 0; i * coins[index] <= rest; i++) {

            sum += find(coins,index+1,rest - i*coins[index]);
        }

        return sum;
    }

    public static void main(String[] args) {

        _518_零钱兑换_II change = new _518_零钱兑换_II();
        // [3,5,7,8,9,10,11]

//        int count = change.change(500, new int[]{3,5,7,8,9,10,11});
//        int count = change.change(10, new int[]{10});
        int count = change.change(5, new int[]{1,2,5});

        System.out.println(count);


    }
}
